﻿//------------------------------------------------------------------------------
// Java implementation:
//
// A stable, adaptive, iterative mergesort that requires far fewer than
// n lg(n) comparisons when running on partially sorted arrays, while
// offering performance comparable to a traditional mergesort when run
// on random arrays.  Like all proper mergesorts, this sort is stable and
// runs O(n log n) time (worst case).  In the worst case, this sort requires
// temporary storage space for n/2 object references; in the best case,
// it requires only a small constant amount of space.
// 
// This implementation was adapted from Tim Peters's list sort for
// Python, which is described in detail here:
// http://svn.python.org/projects/python/trunk/Objects/listsort.txt
// 
// Tim's C code may be found here:
// http://svn.python.org/projects/python/trunk/Objects/listobject.c
// 
// The underlying techniques are described in this paper (and may have
// even earlier origins):
// 
// "Optimistic Sorting and Information Theoretic Complexity"
// Peter McIlroy
// SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
// pp 467-474, Austin, Texas, 25-27 January 1993.
// 
// While the API to this class consists solely of static methods, it is
// (privately) instantiable; a TimSort instance holds the state of an ongoing
// sort, assuming the input array is large enough to warrant the full-blown
// TimSort. Small arrays are sorted in place, using a binary insertion sort.
// 
// author: Josh Bloch
//------------------------------------------------------------------------------
// C# implementation:
//
// This implementation was adapted from Josh Bloch array sort for Java, 
// which has been found here:
// http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co
// 
// author: Milosz Krajewski
//------------------------------------------------------------------------------


namespace TimSort;

using System;
using System.Diagnostics;

/// <summary>
/// TimSortBase is base class for all TimSort specific classes. It contains common methods.
/// Should not be used directly.
/// </summary>
/// <typeparam name="TList">The type of the list.</typeparam>
/// <typeparam name="TItem">The type of the item.</typeparam>
internal abstract class TimSortBase<TList, TItem>
{
    /// <summary>Initializes a new instance of the <see cref="TimSortBase&lt;TList, TItem&gt;"/> class.</summary>
    /// <param name="array">The array.</param>
    /// <param name="arrayLength">Length of the array.</param>
    protected TimSortBase(TList array, int arrayLength)
    {
        _array = array;
        _arrayLength = arrayLength;

        // Allocate temp storage (which may be increased later if necessary)
        var mergeBufferLength =
            arrayLength < 2*INITIAL_TMP_STORAGE_LENGTH
                ? arrayLength >> 1
                : INITIAL_TMP_STORAGE_LENGTH;
        _mergeBuffer = new TItem[mergeBufferLength];

        // Allocate runs-to-be-merged stack (which cannot be expanded).  The
        // stack length requirements are described in listsort.txt.  The C
        // version always uses the same stack length (85), but this was
        // measured to be too expensive when sorting "mid-sized" arrays (e.g.,
        // 100 elements) in Java.  Therefore, we use smaller (but sufficiently
        // large) stack lengths for smaller arrays.  The "magic numbers" in the
        // computation below must be changed if MIN_MERGE is decreased.  See
        // the MIN_MERGE declaration above for more information.
        var stackLength =
            arrayLength < 120 ? 5 :
            arrayLength < 1542 ? 10 :
            arrayLength < 119151 ? 19 :
            40;
        _runBase = new int[stackLength];
        _runLength = new int[stackLength];
    }

    /// <summary>
    /// This is the minimum sized sequence that will be merged.  Shorter
    /// sequences will be lengthened by calling BinarySort.  If the entire
    /// array is less than this length, no merges will be performed.
    /// This constant should be a power of two.  It was 64 in Tim Peter's C
    /// implementation, but 32 was empirically determined to work better in
    /// this implementation.  In the unlikely event that you set this constant
    /// to be a number that's not a power of two, you'll need to change the
    /// <c>minRunLength</c> computation.
    /// If you decrease this constant, you must change the stackLen
    /// computation in the TimSort constructor, or you risk an
    /// ArrayOutOfBounds exception.  See listsort.txt for a discussion
    /// of the minimum stack length required as a function of the length
    /// of the array being sorted and the minimum merge sequence length.
    /// </summary>
    protected const int MIN_MERGE = 32;

    /// <summary>
    /// When we get into galloping mode, we stay there until both runs win less
    /// often than MIN_GALLOP consecutive times.
    /// </summary>
    protected const int MIN_GALLOP = 7;

    /// <summary>
    /// Maximum initial size of tmp array, which is used for merging. 
    /// The array can grow to accommodate demand.
    /// Unlike Tim's original C version, we do not allocate this much storage
    /// when sorting smaller arrays. This change was required for performance.
    /// </summary>
    protected const int INITIAL_TMP_STORAGE_LENGTH = 256;

    /// <summary>The array being sorted.</summary>
    protected readonly TList _array;

    /// <summary>Cached length of array, it won't change.</summary>
    protected readonly int _arrayLength;

    /// <summary>
    /// This controls when we get *into* galloping mode.  It is initialized
    /// to MIN_GALLOP.  The mergeLo and mergeHi methods nudge it higher for
    /// random data, and lower for highly structured data.
    /// </summary>
    protected int _minGallop = MIN_GALLOP;

    /// <summary>
    /// Temp storage for merges.
    /// </summary>
    protected TItem[] _mergeBuffer;

    /// <summary>
    /// A stack of pending runs yet to be merged.  Run i starts at
    /// address base[i] and extends for len[i] elements.  It's always
    /// true (so long as the indices are in bounds) that:
    /// <c>runBase[i] + runLen[i] == runBase[i + 1]</c>
    /// so we could cut the storage for this, but it's a minor amount,
    /// and keeping all the info explicit simplifies the code.
    /// </summary>
    protected int _stackSize; // = 0; // Number of pending runs on stack

    protected int[] _runBase;
    protected int[] _runLength;

    /// <summary>
    /// Returns the minimum acceptable run length for an array of the specified length. Natural runs shorter than this 
    /// will be extended with BinarySort.
    /// Roughly speaking, the computation is:
    /// If <c>n &lt; MIN_MERGE</c>, return n (it's too small to bother with fancy stuff).
    /// Else if n is an exact power of 2, return <c>MIN_MERGE/2</c>.
    /// Else return an int k, <c>MIN_MERGE/2 &lt;= k &lt;= MIN_MERGE</c>, such that <c>n/k</c> is close to, but strictly 
    /// less than, an exact power of 2. For the rationale, see listsort.txt.
    /// </summary>
    /// <param name="n">the length of the array to be sorted.</param>
    /// <returns>the length of the minimum run to be merged.</returns>
    protected static int GetMinimumRunLength(int n)
    {
        Debug.Assert(n >= 0);
        var r = 0; // Becomes 1 if any 1 bits are shifted off
        while (n >= MIN_MERGE)
        {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    /// <summary>
    /// Merges the two runs at stack indices i and i+1. 
    /// Run i must be the penultimate or antepenultimate run on the stack. 
    /// In other words, i must be equal to stackSize-2 or stackSize-3.
    /// </summary>
    /// <param name="runIndex">stack index of the first of the two runs to merge.</param>
    protected abstract void MergeAt(int runIndex);

    /// <summary>
    /// Examines the stack of runs waiting to be merged and merges adjacent runs until the stack invariants are
    /// reestablished: 
    /// <c><![CDATA[1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] ]]></c> and 
    /// <c><![CDATA[2. runLen[i - 2] > runLen[i - 1] ]]></c>
    /// This method is called each time a new run is pushed onto the stack,
    /// so the invariants are guaranteed to hold for i &lt; stackSize upon
    /// entry to the method.
    /// </summary>
    protected void MergeCollapse()
    {
        while (_stackSize > 1)
        {
            var n = _stackSize - 2;

            if (n > 0 && _runLength[n - 1] <= _runLength[n] + _runLength[n + 1])
            {
                if (_runLength[n - 1] < _runLength[n + 1])
                {
                    n--;
                }
                MergeAt(n);
            }
            else if (_runLength[n] <= _runLength[n + 1])
            {
                MergeAt(n);
            }
            else
            {
                break; // Invariant is established
            }
        }
    }

    /// <summary>
    /// Merges all runs on the stack until only one remains.  This method is called once, to complete the sort.
    /// </summary>
    protected void MergeForceCollapse()
    {
        while (_stackSize > 1)
        {
            var n = _stackSize - 2;
            if (n > 0 && _runLength[n - 1] < _runLength[n + 1])
            {
                n--;
            }
            MergeAt(n);
        }
    }

    /// <summary>
    /// Pushes the specified run onto the pending-run stack.
    /// </summary>
    /// <param name="runBase">index of the first element in the run.</param>
    /// <param name="runLength">the number of elements in the run.</param>
    protected void PushRun(int runBase, int runLength)
    {
        _runBase[_stackSize] = runBase;
        _runLength[_stackSize] = runLength;
        _stackSize++;
    }

    /// <summary>
    /// Ensures that the external array tmp has at least the specified
    /// number of elements, increasing its size if necessary.  The size
    /// increases exponentially to ensure amortized linear time complexity.
    /// </summary>
    /// <param name="minCapacity">the minimum required capacity of the tmp array.</param>
    /// <returns>tmp, whether or not it grew</returns>
    protected TItem[] EnsureCapacity(int minCapacity)
    {
        if (_mergeBuffer.Length < minCapacity)
        {
            // Compute smallest power of 2 > minCapacity
            var newSize = minCapacity;
            newSize |= newSize >> 1;
            newSize |= newSize >> 2;
            newSize |= newSize >> 4;
            newSize |= newSize >> 8;
            newSize |= newSize >> 16;
            newSize++;

            newSize = newSize < 0 ? minCapacity : Math.Min(newSize, _arrayLength >> 1);

            _mergeBuffer = new TItem[newSize];
        }
        return _mergeBuffer;
    }

    /// <summary>
    /// Checks that fromIndex and toIndex are in range, and throws an
    /// appropriate exception if they aren't.
    /// </summary>
    /// <param name="arrayLen">the length of the array.</param>
    /// <param name="fromIndex">the index of the first element of the range.</param>
    /// <param name="toIndex">the index after the last element of the range.</param>
    protected static void CheckRange(int arrayLen, int fromIndex, int toIndex)
    {
        if (fromIndex > toIndex)
        {
            throw new ArgumentException($"fromIndex({fromIndex}) > toIndex({toIndex})");
        }
        if (fromIndex < 0)
        {
            throw new IndexOutOfRangeException($"fromIndex ({fromIndex}) is out of bounds");
        }
        if (toIndex > arrayLen)
        {
            throw new IndexOutOfRangeException($"toIndex ({toIndex}) is out of bounds");
        }
    }

    /// <summary>Reverse the specified range of the specified array.</summary>
    /// <param name="array">the array in which a range is to be reversed.</param>
    /// <param name="lo">the index of the first element in the range to be reversed.</param>
    /// <param name="hi">the index after the last element in the range to be reversed.</param>
    protected static void ArrayReverseRange(TItem[] array, int lo, int hi)
    {
        Array.Reverse(array, lo, hi - lo);
    }

    /// <summary>Copies specified array range.</summary>
    /// <param name="buffer">The buffer.</param>
    /// <param name="sourceIndex">Index of the source.</param>
    /// <param name="targetIndex">Index of the target.</param>
    /// <param name="length">The length.</param>
    protected static void ArrayCopyRange(TItem[] buffer, int sourceIndex, int targetIndex, int length)
    {
        Array.Copy(buffer, sourceIndex, buffer, targetIndex, length);
    }

    /// <summary>Copies specified array range.</summary>
    /// <param name="source">The source.</param>
    /// <param name="sourceIndex">Index of the source.</param>
    /// <param name="target">The target.</param>
    /// <param name="targetIndex">Index of the target.</param>
    /// <param name="length">The length.</param>
    protected static void ArrayCopyRange(TItem[] source, int sourceIndex, TItem[] target, int targetIndex, int length)
    {
        Array.Copy(source, sourceIndex, target, targetIndex, length);
    }
}
